/*************************************************************************
	> File Name: oj-489.cpp
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2021年02月03日 星期三 23时12分08秒
 ************************************************************************/

#include <iostream>
using namespace std;

int main() {
    int n, odd[2] = {0, 1}, even[2] = {0, 8};
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        odd[i % 2] = odd[(i - 1) % 2] * 9 + even[(i - 1) % 2];
        even[i % 2] = odd[(i - 1) % 2] + 9 * even[(i - 1) % 2];
        odd[i % 2] %= 12345;
        even[i % 2] %= 12345;
    }
    cout << even[n % 2] << endl;
    return 0;
}
